package sword.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 * 链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftySevenII {
    /**
     * 暴力法，直接从1开始累加。当等于target时，起点位置++，终点位置回归到起点位置的后一位。
     * 执行时间仅超过10%
     * */
    class Solution {
        public int[][] findContinuousSequence(int target) {
            List<List<Integer>> result = new ArrayList<>();

            for(int i=1, j=i+1, sum = i; j <= (target+1) / 2; j++){
                sum+=j;
                if(sum == target){
                    result.add(buildArrayByRang(i, j));
                    sum = ++i;
                    j = i;
                }else if(sum > target){
                    sum= ++i;
                    j = i;
                }
            }
            int[][] res = new int[result.size()][];
            int index=0;
            for(List<Integer> list : result){
                int[] r = new int[list.size()];
                int k = 0;
                for(Integer l : list){
                    r[k++] = l;
                }
                res[index++] = r;
            }
            return res;
        }

        private List<Integer> buildArrayByRang(int start, int end){
            List<Integer> list = new ArrayList<>();
            for (int i = start; i <= end; i++) {
                list.add(i);
            }
            return list;
        }
    }

    /**
     * 双指针法。
     * 使用两个指针，一个start指针指向数组开始下标，一个end指针指向数组结束下标。
     * 如果当前范围内的数据加一块比target小，那么end指针++，反之，start指针++
     * 执行时间仅超过50%，跟官方的双指针一样
     * */
    class Solution1 {
        public int[][] findContinuousSequence(int target) {
            if(target < 3){
                return new int[][]{};
            }
            int start = 1;
            int end = 2;
            int sum = start + end;
            List<List<Integer>> res = new ArrayList<>();
            while (end <= (target+1) / 2){
                if(sum == target){
                    res.add(buildArrayByRang(start, end));
                    sum-=start;
                    start++;
                }else if(sum > target){
                    sum-=start;
                    start++;
                }else {
                    end++;
                    sum+=end;
                }
            }
            int[][] result = new int[res.size()][];
            int index=0;
            for(List<Integer> list : res){
                int[] r = new int[list.size()];
                int k = 0;
                for(Integer l : list){
                    r[k++] = l;
                }
                result[index++] = r;
            }
            return result;

        }
        private List<Integer> buildArrayByRang(int start, int end){
            List<Integer> list = new ArrayList<>();
            for (int i = start; i <= end; i++) {
                list.add(i);
            }
            return list;
        }

    }
}
